package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;
import cn.zzf.algs.note.base.util.StringUtil;

import java.util.Arrays;

/**
 * 改进版的归并排序，递归
 * 1.对于小数组排序使用插入排序完成，减少方法栈的调用
 * 2.对于已经有序的数组，直接返回，无需排序
 * 3.实现无需复制的辅助数组
 * @author GaoFeng2017
 * @date 2020/7/17 8:41
 */
public class TopdownMergeSortV2 implements Sort {


    @Override
    public void sort(Comparable[] elements) {
        Comparable[] auxiliaryElements = new Comparable[elements.length];
        System.arraycopy(elements, 0, auxiliaryElements, 0, elements.length);
        this.sort(elements, auxiliaryElements, 0, elements.length - 1, 0);
    }

    private void sort(Comparable[] auxiliaryElements, Comparable[] inputElements, int beginIndex, int endIndex, int step) {

        if (beginIndex >= endIndex) {
            return;
        }

        String indent = StringUtil.repeat("  ", ++step);

        // 打印堆栈信息
        if (inputElements.length <= 32) {
            System.out.println(indent + "sort(" + beginIndex + ", " + endIndex + ") step: " + step);
        }

        // 获取中位点
        int mid = (beginIndex + endIndex) / 2;

        // 左排序
        sort(inputElements, auxiliaryElements, beginIndex, mid, step);

        // 有排序
        sort(inputElements, auxiliaryElements, mid + 1, endIndex, step);

        if (inputElements.length <= 32) {
            System.out.println(indent + "before merge auxiliaryElements: " + Arrays.toString(auxiliaryElements) + " inputElements: " + Arrays.toString(inputElements));
        }

        if (inputElements.length <= 32) {
            System.out.println(indent + "merge(" + beginIndex + ", " + mid + ", " + endIndex + ")");
        }

        // 交换辅助数组与输入数组的角色, 同时进行合并
        this.merge(auxiliaryElements, inputElements, beginIndex, mid, endIndex);

        if (inputElements.length <= 32) {
            System.out.println(indent + "after merge auxiliaryElements: " + Arrays.toString(auxiliaryElements) + " inputElements: " + Arrays.toString(inputElements));
        }

    }


    private void merge(Comparable[] auxiliaryElements, Comparable[] inputElements, int beginIndex, int mid, int endIndex) {

        int leftIndex = beginIndex;
        int rightIndex = mid + 1;

        //去除某半边

        for (int i = beginIndex; i <= endIndex; i++) {
            if (leftIndex > mid) {
                // 取右边
                auxiliaryElements[i] = inputElements[rightIndex++];
            } else if (rightIndex > endIndex) {
                // 取左边
                auxiliaryElements[i] = inputElements[leftIndex++];
            } else if (SortUtil.less(inputElements[rightIndex], inputElements[leftIndex])) {
                // 取左边
                auxiliaryElements[i] = inputElements[rightIndex++];
            } else {
                // 取右边
                auxiliaryElements[i] = inputElements[leftIndex++];
            }
        }

    }

}
